class Solution:
    # 方案二：原地更新
    # 时间复杂度：O(mn)
    # 空间复杂度：O(1)
    def gameOfLife(self, board: List[List[int]]) -> None:
        directions = [
            [-1, 0],
            [1, 0],
            [0, -1],
            [0, 1],
            [-1, -1],
            [-1, 1],
            [1, -1],
            [1, 1]
        ]

        m = len(board)
        n = len(board[0])

        # 遍历每个细胞，并确定它最终的状态
        for row in range(m):
            for col in range(n):
                # 对于每一个细胞统计其八个相邻位置里的活细胞数量
                liveNeighbors = 0
                for dir in directions:
                    nextRow = row + dir[0]
                    nextCol = col + dir[1]
                    if nextRow < m and nextCol < n and nextRow >= 0 and nextCol >= 0:
                        if abs(board[nextRow][nextCol]) == 1:
                            liveNeighbors += 1

                # 1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
                if board[row][col] == 1 and (liveNeighbors < 2 or liveNeighbors > 3):
                    board[row][col] = -1
                # 2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
                # 3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
                # 4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
                if board[row][col] == 0 and liveNeighbors == 3:
                    board[row][col] = 2
        # 遍历 board 得到一次更新后的状态
        for row in range(m):
            for col in range(n):
                if board[row][col] > 0:
                    board[row][col] = 1
                else:
                    board[row][col] = 0

    # 方案一：使用辅助数组
    # 时间复杂度：O(mn)
    # 空间复杂度：O(mn)
    def gameOfLife1(self, board: List[List[int]]) -> None:
        directions = [
            [-1, 0],
            [1, 0],
            [0, -1],
            [0, 1],
            [-1, -1],
            [-1, 1],
            [1, -1],
            [1, 1]
        ]

        m = len(board)
        n = len(board[0])
        # 创建复制数组 copyBoard
        copyBoard = [[0 for j in range(n)] for i in range(m)]
        # 从原数组复制一份到 copyBoard 中
        for row in range(m):
            for col in range(n):
                copyBoard[row][col] = board[row][col]
        # 遍历每个细胞，并确定它最终的状态
        for row in range(m):
            for col in range(n):
                # 对于每一个细胞统计其八个相邻位置里的活细胞数量
                liveNeighbors = 0
                for dir in directions:
                    nextRow = row + dir[0]
                    nextCol = col + dir[1]
                    if nextRow < m and nextCol < n and nextRow >= 0 and nextCol >= 0:
                        if copyBoard[nextRow][nextCol] == 1:
                            liveNeighbors += 1

                # 1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
                if copyBoard[row][col] == 1 and (liveNeighbors < 2 or liveNeighbors > 3):
                    board[row][col] = 0
                # 2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
                # 3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
                # 4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
                if copyBoard[row][col] == 0 and liveNeighbors == 3:
                    board[row][col] = 1